/**
 * @file dset.h
 * @author xincz
 * @brief 
 * @version 0.1
 * @date 2021-05-27
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#ifndef __DSET_H__
#define __DSET_H__

#include <vector>

using namespace std;


/**
 * [Link-by-size]
 * Each DisjointSets object represents a family of disjoint sets, where each
 * element has an integer index. It is implemented using up-trees stored in a
 * single vector of ints. Specifically, path compression and union-by-size are
 * used. Each place in the vector represents a node. A nonnegative number is
 * the index of the parent of the current node; a negative number in a root
 * node is the negative of the set size.
 */
class DisjointSets {
private:
    vector<int> parent;
    vector<int> sizes;
    int capacity;

public:
    DisjointSets() : capacity(0) {}


    /**
     * Make a new set containing the root x.
     * @param x The new root.
     */
    void MakeSet(int x);


    /**
     * Creates n unconnected root nodes at the end of the vector.
     * @param num The number of nodes to create.
     */
    void AddElements(int num);


    /**
     * Compress path and find.
     * @return The index of the root of the up-tree in which the parameter
     *  element resides.
     */
    int Find(int elem);


    /**
     * Union-by-size: the smaller (#nodes) should point at the larger.
     * Find the roots of its arguments before combining the trees. If the
     * two sets are the same size, make the tree containing the second
     * argument point to the tree containing the first.
     * 
     * @param a Index of the first element to union.
     * @param b Index of the second element to union.
     */
    void Union(int a, int b);
};

#endif
